Node-pair reliability of network systems with small distances between adjacent nodes

A new method for computing the node-pair reliability of network systems modeled by random graphs with nodes arranged in sequence is presented. It is based on a recursive algorithm using the “sliding window” technique, the window being composed of several consecutive nodes. In a single step, the connectivity probabilities for all nodes included in the window are found. Subsequently, the window is moved one node forward. This process is repeated until, in the last step, the window reaches the terminal node. The connectivity probabilities found at that point are used to compute the node-pair reliability of the network system considered. The algorithm is designed especially for graphs with small distances between adjacent nodes, where the distance between two nodes is defined as the absolute value of the difference between the nodes’ numbers. The maximal distance between any two adjacent nodes is denoted by Γ(G), where G symbolizes a random graph. If Γ(G)=2 then the method can be applied for directed as well as undirected graphs whose nodes and edges are subject to failure. This is important in view of the fact that many algorithms computing network reliability are designed for graphs with failure-prone edges and reliable nodes. If Γ(G)=3 then the method's applicability is limited to undirected graphs with reliable nodes. The main asset of the presented algorithms is their low numerical complexity—O(n), where n denotes the number of nodes.     

不含4圈的最大简单图边数的下界

证明了具有不小于6个顶点的不包含4圈的简单图的最大可能边数的下界是2n-5。     

ELNF演算的解释技术

ＥＬＮＦ演算是我们在ＬＮＦ演算的基础上扩充逻辑程序设计能力而得到的一种函数／逻辑演算系统，它构成了作者设计的函数／逻辑语言ＲＦＵＮＬＯＧ的基础．本文介绍ＥＬＮＦ演算的解释实现技术，包括数据结构、系统结构以及各个模块的设计思想．最后给出了在此解释系统下，几个典型程序的运行时间．     

Automating the identification and analysis of protein {beta}-barrels

ßBarrels are widespread and well-studied featuresof a great many protein structures. In this paper an unsuper-visedmethod for the detection of P-barrels is developed based ontechniques from graph theory. The hydrogen bonded connectivityof ß-sheets is derived using standard pattern recognitiontechniques and expressed as a graph. Barrels correspond to topologicalrings in these connectivity graphs and can thus be identifiedusing ring perception algorithms. Following from this, the characteristictopological structure of a barrel can be expressed using a novelform of reduced nomenclature that counts sequence separationsbetween successive members of the ring set These techniquesare tested by applying them to the detection of barrels in anon-redundant subset of the Brookhaven database. Results indicatethat topological rings do seem to correspond uniquely to ß-barrelsand that the technique, as implemented, finds the majority ofbarrels present in the dataset.     

反编译程序图设计与控制流分析

反编译是一种能将低级语言翻译到高级语言的工具。本文着重介绍反编译代码存储的程序图方法，以及在程序图基础上，对代码程序进行控制流分析、控制结构提取，给出了结构提取的算法；控制流分析过程中的程序图变换。     

转移法色交换

将图Ｇ的着色由一种变为中一种，通常用Ｋｅｍｐｅ法以交换。但是，对于某些情况，用此法无效。针对这个问题，本文提出了一种转移法色交换，它适用于平面图着色，方法直观，清晰且有效。     

Energy minimization and design for testability

The problem of fault detection in general combinational circuits is NP-complete. The only previous result on identifying easily testable circuits is due to Fujiwara who gave a polynomial time algorithm for detecting any single stuck fault inK-bounded circuits. Such circuits may only contain logic blocks with no more thanK input lines and the blocks are so connected that there is no reconvergent fanout among them. We introduce a new class of combinational circuits called the (k, K)-circuits and present a polynomial time algorithm to detect any single or multiple stuck fault in such circuits. We represent the circuit as an undirected graphG with a vertex for each gate and an edge between a pair of vertices whenever the corresponding gates have a connection. For a (k, K)-circuit,G is a subgraph of ak-tree, which, by definition, cannot have a clique of size greater thank+1. Basically, this is a restriction on gate interconnections rather than on the function of gates comprising the circuit. The (k, K)-circuits are a generalization of Fujiwara'sK-bounded circuits. Using the bidirectional neural network model of the circuit and the energy function minimization formulation of the fault detection problem, we present a test generation algorithm for single and multiple faults in (k, K)-circuits. This polynomial time aggorithm minimizes the energy function by recursively eliminating the variables.     

Integrating integer programming and probabilistic deduction graphs for probabilistic reasoning

Optimal solutions of several variants of the probabilistic reasoning problem were found by a new technique that integrates integer programming and probabilistic deduction graphs (PDG). PDGs are extended from deduction graphs of the and-type via normal deduction graphs. The foregoing variants to be solved can involve multiple hypotheses and multiple evidences where the former is given and the latter is unknown and being found or vice versa. The relationship among these hypotheses and evidences with possible intermediaries is represented by a causal graph. The proposed method can handle a large causal graph of any type and find an optimal solution by invoking a linear integer programming package. In addition, formulating the reasoning problem to fit integer programming takes a polynomial time. H.-L. Li was visiting the Department of Computer Sciences, University of North Texas in 1988–1989. He is with the Institute of Information Management, National Chiao Tung University, Hsinchu, Taiwan, R.O.C.     

一种椭圆弧长的作图求解法及其误差分析

本文给出了一种椭圆弧长的作图求解方法,即由作图求得椭圆弧长的近似值。通过对100个椭圆弧长的求解结果表明,由此方法求得的椭圆弧长的误差甚小,从而在相当高的精度范围内,提供了一种工程中适用并且简单易行的求解椭圆弧长的方法。